package main.leetcode.offer.firstround.from03to50;

import java.util.Arrays;

/**
 * 40.最小的k个数
 *
 * <p>输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 *
 * <p>
 *
 * <p>示例 1：输入：arr = [3,2,1], k = 2 输出：[1,2] 或者 [2,1]
 *
 * <p>示例 2：输入：arr = [0,1,2,1], k = 1 输出：[0]
 *
 * <p>限制：0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex40 {
    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(
                        new ex40().getLeastNumbers(new int[] {0, 0, 2, 3, 2, 1, 1, 2, 0, 4}, 9)));
    }

    //  public int[] getLeastNumbers(int[] arr, int k) {
    //    if (arr.length == 1 && k > 0) return arr;
    //    Arrays.sort(arr);
    //    int[] res = new int[k];
    //    for (int i = 0; i < k; i++) res[i] = arr[i];
    //    return res;
    //  }

    //  // 大顶堆实现
    //  private int k;
    //  public int[] getLeastNumbers(int[] arr, int k) {
    //    if (k == 0) return new int[0];
    //    if (arr.length == 1) return arr;
    //    int[] heap = new int[k];
    //    int i;
    //    this.k = k;
    //    for (i = 0; i < k; i++) heap[i] = arr[i];
    //    buildHeap(heap);
    //    for (i = k; i < arr.length; i++)
    //      if (arr[i] < heap[0]) {
    //        heap[0] = arr[i];
    //        heapify(heap, 0); // 堆维护
    //      }
    //    return heap;
    //  }
    //
    //  // 建堆
    //  // 堆——完整二叉树
    //  private void buildHeap(int[] heap) {
    //    int last = k - 1;
    //    int start = (last - 1) / 2;
    //    while (start >= 0) heapify(heap, start--);
    //  }
    //
    //  // 堆维护
    //  private void heapify(int[] heap, int i) {
    //    if (i > k) return;
    //    int left = (i << 1) + 1, right = left + 1; // 左右孩子
    //    // 寻找栈顶（最大值的下标
    //    int max = i;
    //    if (left < k && heap[max] < heap[left]) max = left;
    //    if (right < k && heap[max] < heap[right]) max = right;
    //    if (max != i) {
    //      swap(heap, max, i);
    //      heapify(heap, max);
    //    }
    //  }
    //
    //  private void swap(int[] heap, int i, int j) {
    //    heap[i] = heap[i] + heap[j] - (heap[j] = heap[i]);
    //  }

    // 快速排序
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0) return new int[0];
        if (arr.length == 1 || arr.length == k) return arr;
        int left = 0, right = arr.length - 1;
        int mid = partion(arr, left, right);
        while (mid != k) {
            if (k < mid) right = mid - 1;
            else left = mid + 1;
            mid = partion(arr, left, right);
        }
        int[] res = new int[k];
        System.arraycopy(arr, 0, res, 0, k);
        return res;
    }

    private int partion(int[] arr, int left, int right) {
        int val = arr[left];
        int i = left, j = right + 1;
        while (true) {
            while (arr[++i] < val && i < right) ;
            while (arr[--j] > val && j > left) ;
            if (i >= j) break;
            swap(arr, i, j);
        }
        swap(arr, left, j);
        return j;
    }

    private void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] + arr[j] - (arr[j] = arr[i]);
    }
}
